#include"regex.h"
#include<sstream>

using std::map;

RegExp::RegExp() {}
	
RegExp::RegExp(RegExp const & re) {}
	
RegExp::~RegExp() {}
	
EmptyRegExp::EmptyRegExp() {}
	
EmptyRegExp::EmptyRegExp(EmptyRegExp const & re) {}
	
RegExp * EmptyRegExp::copy() const {
	return new EmptyRegExp();
}
	
EmptyRegExp::~EmptyRegExp() {}
	
bool EmptyRegExp::match(string const & s) const {
	return false;
}

string EmptyRegExp::toString() const {
	return "{0}";
}

NFA EmptyRegExp::toNFA() const {
	return NFA();
}

//RegExp * EmptyRegExp::subst(map<unsigned, RegExp *> const & ss) const {
//	return copy();
//}
//
//NTRegExp const * EmptyRegExp::locateNT() const {
//	return 0;
//}

LiteralRegExp::LiteralRegExp(string const & s) : contents(s) {}

LiteralRegExp::LiteralRegExp(LiteralRegExp const & re) : contents(re . contents) {}
	
RegExp * LiteralRegExp::copy() const {
	return new LiteralRegExp(*this);
}
	
LiteralRegExp::~LiteralRegExp() {}
	
bool LiteralRegExp::match(string const & s) const {
	return (s == contents);
}

string LiteralRegExp::toString() const {
	return contents;
}

NFA LiteralRegExp::toNFA() const {
	NFA res;
	std::stringstream ss;
	unsigned nextstate = NFA::names . addName("S"), prevstate = 0;
	res . starting . insert (nextstate);
	for( unsigned i = 0; i < contents . length(); ++i ) {
		std::swap(prevstate, nextstate);
		ss << i;
		nextstate = NFA::names . addName((string)"S" + ss . str());
		res . rules .insert (std::make_pair(std::make_pair(prevstate, contents[i]), nextstate));
	}
	res . accepting . insert(nextstate);
	return res;
}

//RegExp * LiteralRegExp::subst(map<unsigned, RegExp *> const & ss) const {
//	return copy();
//}
//
//NTRegExp const * LiteralRegExp::locateNT() const {
//	return 0;
//}

AlterRegExp::AlterRegExp(RegExp * l, RegExp * r) : left(l ? l : new EmptyRegExp()), right(r ? r : new EmptyRegExp()) {}
	
AlterRegExp::AlterRegExp(AlterRegExp const & re) : left(re . left -> copy()), right(re . right -> copy()) {}
	
RegExp * AlterRegExp::copy() const {
	return new AlterRegExp(*this);
}
	
AlterRegExp::~AlterRegExp() { delete left; delete right;}

bool AlterRegExp::match(string const & s) const {
	return (left -> match(s) || right -> match(s));
}

string AlterRegExp::toString() const {
	return (string)"(" + left -> toString() + (string)"|" + right -> toString() + (string)")";
}

NFA AlterRegExp::toNFA() const {
	NFA res1 = left -> toNFA();
	NFA res2 = right -> toNFA();
	return res1 | res2;
}

//RegExp * AlterRegExp::subst(map<unsigned, RegExp *> const & ss) const {
//	return new AlterRegExp(left -> subst(ss), right -> subst(ss));
//}
//
//NTRegExp const * AlterRegExp::locateNT() const {
//	NTRegExp const * temp = left -> locateNT();
//	return temp ? temp : right -> locateNT();
//}

KleeneRegExp::KleeneRegExp(RegExp * c) : contents(c ? c : new EmptyRegExp()) {}
	
KleeneRegExp::KleeneRegExp(KleeneRegExp const & re) : contents(re . contents -> copy()) {}
	
RegExp * KleeneRegExp::copy() const {
	return new KleeneRegExp(*this);
}
	
KleeneRegExp::~KleeneRegExp() { delete contents; }

bool KleeneRegExp::match(string const & s) const {
	if (s . length() == 0) return true;
	if (s . length() == 1) return contents -> match(s);
	for( unsigned i = s . length(); i > 0; --i ) {
		string l = s . substr(0, i);
		if (contents -> match(l))
			return match(s . substr(i, string :: npos));
	}
	return false;
}

string KleeneRegExp::toString() const {
	return (string)"(" + contents -> toString() + (string)")*";
}

NFA KleeneRegExp::toNFA() const {
	return *(contents -> toNFA());
}

//RegExp * KleeneRegExp::subst(map<unsigned, RegExp *> const & ss) const {
//	return new KleeneRegExp(contents -> subst(ss));
//}
//
//NTRegExp const * KleeneRegExp::locateNT() const {
//	return contents -> locateNT();
//}

ConcatRegExp::ConcatRegExp(RegExp * l, RegExp * r) : left(l ? l : new EmptyRegExp()), right(r ? r : new EmptyRegExp()) {}
	
ConcatRegExp::ConcatRegExp(ConcatRegExp const & re) : left(re . left -> copy()), right(re . right -> copy()) {}
	
RegExp * ConcatRegExp::copy() const {
	return new ConcatRegExp(*this);
}
	
ConcatRegExp::~ConcatRegExp() { delete left; delete right; }

bool ConcatRegExp::match(string const & s) const {
	for( unsigned i = 0; i <= s . length(); ++i ) {
		string l = s . substr(0, i), r = s . substr(i, string :: npos);
		if (left -> match(l) && right -> match(r))
			return true;
	}
	return false;
}

string ConcatRegExp::toString() const {
	return left -> toString() + right -> toString();
}

NFA ConcatRegExp::toNFA() const {
	return (left -> toNFA()) + (right -> toNFA());
}

//RegExp * ConcatRegExp::subst(map<unsigned, RegExp *> const & ss) const {
//	return new ConcatRegExp(left -> subst(ss), right -> subst(ss));
//}
//
//NTRegExp const * ConcatRegExp::locateNT() const {
//	NTRegExp const * temp = left -> locateNT();
//	return temp ? temp : right -> locateNT();
//}

/*NTRegExp::NTRegExp(unsigned c) : contents(c) {}
	
NTRegExp::NTRegExp(NTRegExp const & re) : contents (re . contents) {}
	
RegExp * NTRegExp::copy() const {
	return new NTRegExp(*this);
}

NTRegExp::~NTRegExp() {}
	
bool NTRegExp::match(string const & s) const {
	return false;
}

string NTRegExp::toString() const {
	return "This wasn't supposed to happen.";
}

NFA NTRegExp::toNFA() const {
	return NFA();
}

RegExp * NTRegExp::subst(map<unsigned, RegExp *> const & ss) const {
	map<unsigned, RegExp *>::const_iterator it = ss . find(contents);
	if (it != ss . end())
		return it -> second -> copy();
	else
		return copy();
}

NTRegExp const * NTRegExp::locateNT() const {
	return this;
}*/
